package leetcode;

import java.util.*;

public class LC127 {

    public static int ladderLength(String beginWord, String endWord, List<String> wordList) {
        HashSet<String> wordListSet = new HashSet<>();
        for (int i = 0; i < wordList.size(); i++) {
            wordListSet.add(wordList.get(i));
        }
        HashSet<String> visitedSet = new HashSet<>();
        visitedSet.add(beginWord);
        LinkedList<String> queue = new LinkedList<>();
        queue.addLast(beginWord);
        int step = 0;
        while (!queue.isEmpty()) {
            int qSize = queue.size();
            step ++;
            for (int i = 0; i < qSize; i++) {
                String word = queue.removeFirst();
                for (int j = 0; j < word.length(); j++) {
                    int lEnd = j ;
                    int rStart = j + 1;
                    for (char c = 'a'; c <= 'z'; c ++) {
                        String newWord = word.substring(0,lEnd) + c + word.substring(rStart,word.length());
                        if (wordListSet.contains(newWord) && !visitedSet.contains(newWord)) {
                            if (newWord.equals(endWord)) return step + 1;
                            visitedSet.add(newWord);
                            queue.addLast(newWord);
                        }
                    }
                }
            }
        }
        return 0;
    }

    public static void main(String[] args) {

//        List list = Arrays.asList(new String[]{"hot","dot","dog","lot","log","cog"});
//
//        System.out.println(ladderLength("hit","cog", list));
//
//        System.out.println("as" == "as");
//        String a = new String("aas");
//        String b = new String("aas");
//        System.out.println(a == b);
//        System.out.println(a.equals(b));
//        HashSet<String> hashSet = new HashSet<>();
//        hashSet.add(a);
//        System.out.println(hashSet.contains(b));

        System.out.println("ads1123usjU#%".toUpperCase());

    }

}
